{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deformable Attention\n",
    "\n",
    "- 可变形注意力机制\n",
    "- ref：[《Deformable DETR: Deformable Transformers for End-to-End Object Detection》](http://arxiv.org/abs/2010.04159)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-26T12:30:23.482710300Z",
     "start_time": "2024-07-26T12:30:21.425364400Z"
    }
   },
   "outputs": [],
   "source": [
    "import seaborn as sns\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 经典Transformer中的注意力机制和可变形注意力机制\n",
    "\n",
    "- **经典注意力机制**\n",
    "$$\\begin{aligned}\n",
    "\\text{score} &= \\text{simility}(Q, K) \\\\\n",
    "\\text{output} &= \\text{score} \\cdot V\n",
    "\\end{aligned}$$\n",
    "\n",
    "\n",
    "![可变形注意力机制示意图](https://foruda.gitee.com/images/1721673147889889358/8dfbbbe4_5218658.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "在可变形注意力机制中，`input_spatial_shapes` 主要用于对偏移量进行归一化，从而将采样点的位置限制在一定的范围内。具体而言：\n",
    "\n",
    "1. **偏移量归一化**：在计算采样点时，可变形注意力机制会根据参考点 (`reference_points`) 和偏移量 (`sampling_offsets`) 得出采样点的位置。为了确保采样点位置的合理性，需要使用 `input_spatial_shapes` 对偏移量进行归一化。这样可以避免采样点超出序列的长度或特征图的尺寸。\n",
    "\n",
    "2. **空间坐标映射**：在 `sampling_locations` 的计算中，偏移量被除以 `input_spatial_shapes`，这是为了将偏移量映射到输入序列的空间坐标系统中。`input_spatial_shapes` 代表了输入特征图的空间维度（在你的例子中是 `sequence_length` 和 `1`），通过这个映射，偏移量可以从 [0, 1] 范围内的归一化坐标转换为实际的空间位置。\n",
    "\n",
    "3. **确保采样点的合理性**：由于 `input_spatial_shapes` 的存在，采样点的位置能够确保在合理的范围内，从而避免采样点落在特征图之外，这对于模型的稳定性和有效性非常重要。\n",
    "\n",
    "在实际应用中，`input_spatial_shapes` 通常是表示特征图的宽度和高度，在一维的情况下，它表示序列的长度。而在二维的情况下，它可能是形如 `(H, W)` 的形状，用于对二维的偏移量进行归一化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-08-22T03:03:51.200018700Z",
     "start_time": "2024-08-22T03:03:51.177548600Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "random_indexes tensor([2, 4, 6, 1, 3, 7, 0, 5])\n",
      "offset_normalizer.shape: torch.Size([1, 1, 1, 2])\n",
      "sampling_locations.shape: torch.Size([1, 8, 3, 2])\n",
      "sampled_values.shape: torch.Size([1, 16, 8, 3])\n",
      "sampled_values.shape: torch.Size([1, 16, 8, 3])\n",
      "== deformable attention ==\n",
      "output shape torch.Size([1, 8, 16])\n",
      "deformable attention score shape torch.Size([1, 8, 3])\n"
     ]
    }
   ],
   "source": [
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "class Attention(nn.Module):#经典Transformer注意力机制\n",
    "    \"\"\"为了简化演示，使用1维单头注意力，并且略去Q、K、V和输出的投影\"\"\"\n",
    "    def __init__(self, hidden_size: int = 16):\n",
    "        super(Attention, self).__init__()\n",
    "        self.hidden_size = hidden_size\n",
    "\n",
    "    def compute_score(self, q: torch.Tensor, k: torch.Tensor):\n",
    "        score = torch.matmul(q, k.transpose(-2, -1)) / (self.hidden_size ** 0.5)\n",
    "        return F.softmax(score, dim=-1)\n",
    "\n",
    "    def forward(self, q: torch.Tensor, k: torch.Tensor, v: torch.Tensor):\n",
    "        # 计算注意力分数\n",
    "        score = self.compute_score(q, k)\n",
    "\n",
    "        # 加权求和\n",
    "        output = torch.matmul(score, v)\n",
    "        return output, score\n",
    "    \n",
    "class DeformableAttention(nn.Module):\n",
    "    \"\"\"可变形注意力，这里同样是1维的单头注意力，略去Q、K、V和输出的投影\"\"\"\n",
    "    def __init__(self, hidden_size: int = 16, n_points: int = 2):\n",
    "        super().__init__()\n",
    "        self.hidden_size = hidden_size  # 隐藏层维度，默认为16\n",
    "        self.n_points = n_points  # 可变形注意力的采样点数量,就是公式里的k\n",
    "        # 用于估计偏移量,和图中的对应，是可学习的参数\n",
    "        self.sampling_offsets = nn.Linear(hidden_size, n_points * 1 * 2)  # n_points个偏移量 * n_heads * 2d\n",
    "        # 用于估计权重，和图中的对应\n",
    "        self.attention_weights = nn.Linear(hidden_size, n_points * 1)  # n_points个权重 * n_heads\n",
    "\n",
    "    def esitimate_offset_and_weights(self, q: torch.Tensor, reference_points: torch.Tensor):\n",
    "        \"\"\"根据查询，估计偏移量\n",
    "        Args:\n",
    "            q: Query，形状为(batch_size, sequence_length, hidden_size)\n",
    "            reference_points: 参考点，形状为(batch_size, sequence_length, 2)\n",
    "        Returns:\n",
    "            offset: 偏移量，形状为(batch_size, sequence_length, n_points, 2)\n",
    "            weights: 权重，形状为(batch_size, sequence_length, n_points)\n",
    "        \"\"\"\n",
    "        # 估计偏移量，通过线性层将query映射到偏移量空间\n",
    "        offset = self.sampling_offsets(q)\n",
    "        # 估计权重，通过线性层将query映射到权重空间\n",
    "        weights = self.attention_weights(q)  # 权重的维度为 (batch_size, sequence_length, n_points * 1)\n",
    "        # 权重归一化, 使用softmax使得权重和为1\n",
    "        weights = F.softmax(weights, dim=-1)  # 权重的维度为 (batch_size, sequence_length, n_points)\n",
    "        # 返回的偏移量形状为 (batch_size, sequence_length, n_points, 2)，权重的形状为 (batch_size, sequence_length, n_points)。\n",
    "        return offset.reshape(q.shape[0], q.shape[1], self.n_points, 2), weights\n",
    "    \n",
    "    def ground_truth_offset_and_weights(self, q: torch.Tensor, reference_points: torch.Tensor):\n",
    "        \"\"\"这里为了演示，直接用真实的偏移量，而非去训练一个线性层来估计偏移量，所以这里不重要，可以不看\"\"\"\n",
    "        # 计算偏移量\n",
    "        # random_offset.shape = (batch_size, sequence_length, n_points, 2) 有4个采样点\n",
    "        bs, seq_len , _ = q.shape\n",
    "        random_offset = torch.randint(0, seq_len, (bs, seq_len, self.n_points, 2)) #随机生成偏移量(x,y)\n",
    "        random_offset[:, :, :, 1] = 0. #y方向的偏移量为0\n",
    "        random_offset[:, :, 1, 0] = random_offset[:, :, 1, 0] - reference_points[:, :, 0] * seq_len #第一个采样点x方向的偏移量做了调整\n",
    "        ground_truth_offset = random_indexes - reference_points[:, :, 0] * seq_len #random_indexes是我们真实的偏移量\n",
    "        random_offset[:, :, 0, 0] = ground_truth_offset #ground_truth_offset 表示第0个点的真实偏移量，并将其赋值给 random_offset 的相应位置。最终 offset 是包含所有偏移量的张量。\n",
    "        offset = random_offset       # offset.shape = (batch_size, sequence_length, n_points, 2)\n",
    "\n",
    "\n",
    "        # 计算权重\n",
    "        weights = torch.ones(offset.shape[:-1]) # 权重初始化为1\n",
    "        weights[:, :, 0] = 0.8 # 第一个权重为0.8\n",
    "        weights[:, :, 1:] = 0.2 / (self.n_points - 1) # 其他权重为0.2/(n_points-1)\n",
    "        # 该方法返回的偏移量和权重与估计偏移量和权重类似\n",
    "        return offset, weights\n",
    "        \n",
    "    def forward(self, \n",
    "                q: torch.Tensor, \n",
    "                v: torch.Tensor,  # input feature map x\n",
    "                reference_points: torch.Tensor, \n",
    "                input_spatial_shapes: torch.Tensor,  # 输入特征图的空间形状\n",
    "                using_ground_truth: bool = False):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            q: Query，形状为(batch_size, sequence_length, hidden_size)\n",
    "            v: Value，形状为(batch_size, sequence_length, hidden_size)\n",
    "            reference_points: 参考点，形状为(batch_size, sequence_length, 2)\n",
    "            input_spatial_shapes: 输入的空间形状，这个例子中为 (sequence_length, 1)\n",
    "            using_ground_truth: 布尔值，是否使用真实的偏移量和权重。\n",
    "        Returns:\n",
    "            output: 输出，形状为(batch_size, sequence_length, hidden_size)\n",
    "        \"\"\"\n",
    "        # 根据参数选择使用真实偏移量和权重还是估计的偏移量和权重\n",
    "        if using_ground_truth:\n",
    "            sampling_offsets, weights = self.ground_truth_offset_and_weights(q, reference_points)\n",
    "        else:\n",
    "            sampling_offsets, weights = self.esitimate_offset_and_weights(q, reference_points)\n",
    "        # sampling_offsets.shape = (batch_size, sequence_length, n_points, 2)\n",
    "        # weights.shape = (batch_size, sequence_length, n_points)\n",
    "\n",
    "        # 获得采样点，sampling_locations 的形状为 (batch_size, sequence_length, n_points, 2)。\n",
    "        offset_normalizer = input_spatial_shapes # 输入的空间形状，里边值是(8和1）\n",
    "        # 结合参考点和偏移量计算出采样点的位置。参考点的位置加上偏移量就是最终的采样点位置,reference_points形状为(batch_size, sequence_length, 2)\n",
    "        print(f'offset_normalizer.shape: {offset_normalizer[None, None, None, :].shape}')\n",
    "        # 结合参考点和偏移量计算出采样点的位置。参考点位置加上归一化后的偏移量得到最终采样点位置,这里是增维，类似于unsqueeze\n",
    "        sampling_locations = reference_points[:, :, None, :] + sampling_offsets / offset_normalizer[None, None, None, :]\n",
    "        # 打印采样位置的形状，用于调试\n",
    "        print(f'sampling_locations.shape: {sampling_locations.shape}')\n",
    "        # 将采样点位置从[0,1]范围映射回输入序列的实际长度\n",
    "        sampling_locations_absolute = sampling_locations * input_spatial_shapes[None, None, None, :]\n",
    "        \n",
    "        # 调整value张量的维度顺序，以便于后续的grid_sample操作\n",
    "        # v.shape bs, seq_len, hidden_size -> bs, hidden_size, seq_len（1,16,8）,hidden_size是16\n",
    "        v = v.permute(0, 2, 1)\n",
    "        # 使用grid_sample从value中采样特征，align_corners=True确保边界对齐，sampled_values 的形状为 (batch_size, sequence_length, n_points, hidden_size)\n",
    "        sampled_values = F.grid_sample(v.unsqueeze(-1), sampling_locations, align_corners=True)\n",
    "        # 打印采样值的形状，用于调试\n",
    "        print(f'sampled_values.shape: {sampled_values.shape}')\n",
    "        # 调整采样值的维度顺序，以便于后续的加权求和\n",
    "        # sampled_values.shape = (bs, hidden_size, seq_len, n_points) -> (bs, seq_len, n_points, hidden_size)\n",
    "        print(f'sampled_values.shape: {sampled_values.shape}')\n",
    "        sampled_values = sampled_values.permute(0, 2, 3, 1)#(bs, seq_len, n_points, hidden_size)\n",
    "        # 对采样的特征值进行加权求和，得到最终的输出 output，形状为 (batch_size, sequence_length, hidden_size)。\n",
    "        output = torch.sum(sampled_values * weights.unsqueeze(-1), dim=-2)\n",
    "\n",
    "        # 返回输出和调试信息（采样位置和权重）\n",
    "        return output, (sampling_locations_absolute, weights)  # output(bs, seq_len, hidden_size)\n",
    "\n",
    "    \n",
    "# 对应Query q: 用来计算采样的偏移量 (sampling_offsets) 和注意力权重 (attention_weights)。\n",
    "dummy_query = torch.randn(1, 8, 16)  # batch_size=1, sequence_length=8, hidden_size=16\n",
    "#对应 输入特征图 (input feature map x)，backbone（例如ResNet）的输出，形状为 (batch_size, sequence_length, hidden_size)\n",
    "dummy_value = torch.randn(1, 8, 16)  # batch_size=1, sequence_length=8, hidden_size=16\n",
    "# 位置索引\n",
    "indexes = torch.tensor([0, 1, 2, 3, 4, 5, 6, 7]).unsqueeze(0)\n",
    "# 随机索引\n",
    "random_indexes = torch.randperm(8)\n",
    "print(\"random_indexes\", random_indexes)\n",
    "# 这里的 key 是 query 的一个随机排列\n",
    "dummy_key = dummy_query[:, random_indexes]\n",
    "\n",
    "# 初始化注意力\n",
    "attention = Attention()\n",
    "# 计算注意力\n",
    "output, classic_score = attention(\n",
    "    q=dummy_query, \n",
    "    k=dummy_key, \n",
    "    v=dummy_value\n",
    "    )\n",
    "\n",
    "# print(\"== classic attention ==\")\n",
    "# print(\"output shape\", output.shape)\n",
    "# print(\"attention score shape\", classic_score.shape)\n",
    "\n",
    "# 初始化可变形注意力\n",
    "n_points = 3\n",
    "deformable_attention = DeformableAttention(n_points=n_points)\n",
    "# 计算参考点\n",
    "reference_points = torch.tensor([\n",
    "    [0, 0],\n",
    "    [1, 0],\n",
    "    [2, 0],\n",
    "    [3, 0],\n",
    "    [4, 0],\n",
    "    [5, 0],\n",
    "    [6, 0],\n",
    "    [7, 0]\n",
    "]).reshape(1, 8, 2)  # batch_size=1, sequence_length=8, 2D(x,y)\n",
    "reference_points = reference_points / 8 # 参考点的值在 0~1 之间 \n",
    "\n",
    "# 计算注意力,在bevformer的decoder中，q是随机的，v是encoder的输出，k是空的\n",
    "output, (loc, deformable_score) = deformable_attention(\n",
    "    q=dummy_query,\n",
    "    v=dummy_value, \n",
    "    reference_points=reference_points,\n",
    "    input_spatial_shapes=torch.tensor([8, 1]),\n",
    "    using_ground_truth=True\n",
    "    )\n",
    "\n",
    "#上面的loc主要是为了可视化\n",
    "print(\"== deformable attention ==\")\n",
    "print(\"output shape\", output.shape) #通过可变形注意力机制生成的加权特征值，形状为 (batch_size, sequence_length, hidden_size)。\n",
    "print(\"deformable attention score shape\", deformable_score.shape) # 是注意力权重，形状为 (batch_size, sequence_length, n_points)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "`torch.nn.functional.grid_sample` 是 PyTorch 中的一个函数，主要用于对图像或特征图进行采样和变换。它常用于图像处理、计算机视觉任务中，特别是在实现空间变换网络（Spatial Transformer Networks, STN）时。\n",
    "\n",
    "### 核心作用\n",
    "`grid_sample` 函数可以根据输入的采样网格 (`grid`) 对输入张量 (`input`) 进行采样，返回经过变换后的输出张量。它支持各种形式的空间变换，如仿射变换、透视变换等。\n",
    "\n",
    "### 参数\n",
    "- **input**: 输入张量，通常是 4D 张量，形状为 `(N, C, H, W)`，分别表示批次大小、通道数、高度和宽度。\n",
    "- **grid**: 采样网格，通常也是 4D 张量，形状为 `(N, H_out, W_out, 2)`，表示在输出空间中每个位置对应输入空间的位置。每个位置用一对坐标 (x, y) 来表示，其中 x 和 y 的范围是 [-1, 1]，分别对应输入图像的左上角和右下角。\n",
    "\n",
    "### 工作原理\n",
    "`grid_sample` 函数根据 `grid` 中的坐标，从 `input` 张量中采样相应的像素值。采样时可以选择不同的插值方式（例如双线性插值）和填充方式（例如边界填充或反射填充）。\n",
    "\n",
    "### 主要选项\n",
    "- **mode**: 插值模式，默认是 `'bilinear'`，可以选择 `'nearest'`（最近邻插值）或 `'bilinear'`（双线性插值）。\n",
    "- **padding_mode**: 当采样点落在输入范围之外时的填充模式。选项有 `'zeros'`（填充0）、 `'border'`（使用边界值填充）、`'reflection'`（反射填充）。\n",
    "- **align_corners**: 如果为 `True`，则 `grid` 的坐标对齐方式是角点对齐；如果为 `False`，则是中心点对齐。\n",
    "\n",
    "### 示例\n",
    "```python\n",
    "import torch\n",
    "import torch.nn.functional as F\n",
    "\n",
    "# 创建一个示例输入张量\n",
    "input = torch.arange(1., 10.).view(1, 1, 3, 3)\n",
    "\n",
    "# 创建一个采样网格\n",
    "grid = torch.tensor([[[[-1, -1], [1, -1], [-1, 1], [1, 1]]]]).view(1, 2, 2, 2)\n",
    "\n",
    "# 应用 grid_sample\n",
    "output = F.grid_sample(input, grid, mode='bilinear', padding_mode='zeros', align_corners=True)\n",
    "\n",
    "print(output)\n",
    "```\n",
    "\n",
    "### 输出\n",
    "```plaintext\n",
    "tensor([[[[1., 3.],\n",
    "          [7., 9.]]]])\n",
    "```\n",
    "\n",
    "### 应用场景\n",
    "- **图像变换**: `grid_sample` 常用于应用仿射变换、透视变换或其他空间变换。\n",
    "- **空间变换网络（STN）**: STN 是一种可以学习空间变换的网络结构，`grid_sample` 是其核心操作之一，用于根据变换参数生成变换后的图像或特征图。\n",
    "\n",
    "通过 `grid_sample` 函数，你可以灵活地对图像或特征图进行采样和变换，帮助神经网络适应不同的视角或尺度变化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-08-15T12:17:17.312388400Z",
     "start_time": "2024-08-15T12:17:17.292411700Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[[[1., 2., 3.],\n",
      "          [4., 5., 6.],\n",
      "          [7., 8., 9.]]]])\n",
      "tensor([[[[-1., -1.],\n",
      "          [ 1., -1.]],\n",
      "\n",
      "         [[-1.,  1.],\n",
      "          [ 1.,  1.]]]])\n",
      "tensor([[[[1., 3.],\n",
      "          [7., 9.]]]])\n"
     ]
    }
   ],
   "source": [
    "# 创建一个示例输入张量\n",
    "input = torch.arange(1., 10.).view(1, 1, 3, 3)\n",
    "print(input)\n",
    "# 创建一个采样网格\n",
    "grid = torch.tensor([[[[-1, -1], [1, -1], [-1, 1], [1, 1]]]]).view(1, 2, 2, 2).float()\n",
    "print(grid)\n",
    "# 应用 grid_sample\n",
    "output = F.grid_sample(input, grid, mode='bilinear', padding_mode='zeros', align_corners=True)\n",
    "\n",
    "print(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 可视化注意力图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-08-22T03:08:04.587035100Z",
     "start_time": "2024-08-22T03:08:03.989170500Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA9MAAAHvCAYAAABXKoy6AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAWbBJREFUeJzt3Ql8VNXZ+PFnEkiQJQFkEwzgBohsNgiC4gqmaFFsVYrWRFTqhiKp719wARUlrkhbUQQBbRWhtYpWESpoXCoKQmmBIopsEWVTIQIvAWfu//McnXlnskAmzGHuvfP7+jkfnJs7d84MYZ57tucEHMdxBAAAAAAAVFta9U8FAAAAAACKxjQAAAAAAHGiMQ0AAAAAQJxoTAMAAAAAECca0wAAAAAAxInGNAAAAAAAcaIxDQAAAABAnGhMAwAAAAAQJxrTAAAAAADEicY0AAAAAABxojENAAAAAPC0iRMnStu2baVOnTrSs2dPWbRo0QHPnzBhgrRv316OOOIIycnJkREjRsjevXvjek0a0wAAAAAAz5o1a5YUFhbKmDFjZOnSpdK1a1fJy8uTrVu3Vnr+jBkzZOTIkeb8VatWydSpU8017rjjjrheN+A4jpOg9wAAAAAAwGGlI9GnnHKKPPHEE+ZxKBQyo80333yzaTSXN2zYMNOIXrBgQeTY7373O/n444/lgw8+qPbr1kpQ/QEAiNBpUvv27bN2/YyMDDONCwAA+DPeO44jgUAg5lhmZqYp0fT1lyxZIqNGjYocS0tLk759+8rChQsrvXbv3r3l+eefN1PBe/ToIWvXrpU5c+bIlVdeGVcdaUwDABIeWI9pU182bw1ae40WLVrIunXraFADAODTeF+/fn3ZtWtXzDGdln3PPffEHNu+fbsEg0Fp3rx5zHF9/Omnn1Z67csvv9w87/TTTzeN9h9++EGuv/76uKd505gGACSU9hBrYF23pI1kNUh8ao7S70NyTO4G8zo0pgEA8F+8L/0p1peUlEhWVlbkePlR6ZoqLi6WcePGyZNPPmmmiK9Zs0aGDx8uY8eOlbvvvrva16ExDQCwQgOrjcY0AABIjXiflZUV05iuTJMmTSQ9PV22bNkSc1wf60y2ymiDWad0X3vtteZx586dZffu3fLb3/5W7rzzTjNNvDq4ywEAWBF0QtYKAABwh2CSY73mUcnNzY1JJqYJyPRxr169Kn3Onj17KjSYtUGu4snPzcg0AAAAAMCzCgsLpaCgQLp3724Siuke0jrSPGTIEPPz/Px8adWqlRQVFZnHAwYMkPHjx8vJJ58cmeato9V6PNyorg4a0wAAK0LimGLjugAAwL/xPhTn9QYNGiTbtm2T0aNHy+bNm6Vbt24yd+7cSFKyjRs3xoxE33XXXSZTuP65adMmadq0qWlIP/DAA3G9LvtMAwASqrS0VLKzs2Xz6tbWEpC1aL9Rdu7cedB1VAAAwHvxvtQjsZ6RaQCAFSHzn53rAgAA/8b7kEdiPQnIAAAAAACIEyPTAAArgo5jio3rAgAA/8b7oEdiPY1pAIAVJCADAMD/Qi5IQJYsTPMGAAAAACBOjEwDAKzQXuUgI9MAAPhayEK890qsZ2QaAAAAAIA4MTINALCCNdMAAPhfiDXTAAAAAACguhiZBgBYwdZYAAD4XzCFt8ZiZBoAAAAAgDgxMg0AsCL0U7FxXQAA4N94HxJvoDENALAiaGlrLBvXBAAA7on3QY/EeqZ5AwAAAAAQJ0amAQBWBJ0fi43rAgAA/8b7oEdiPSPTAAAAAADEiZFpAIAVJCADAMD/QimcgIyRaQAAAAAA4sTINADAipAEJCgBK9cFAAD+jfchj8R6RqYBAAAAAIgTI9MAACtCzo/FxnUBAIB/433II7GexjQAwIqgpWneNq4JAADcE++DHon1TPMGAAAAACBOjEwDAKxgZBoAAP8LMjINAAAAAACqi5FpAIAVISdgio3rAgAA/8b7kEdiPSPTAAAAAADEiZFpAIAVrJkGAMD/gqyZBgAAAAAA1cXINADAiqCkmZL46wIAAD/H+6B4A41pAIAVjqUEZHpdAADg33jveCTWM80bAAAAAIA4MTINALCCBGQAAPhfkARkwIEVFxdLIBAwfyaLvv4999yTtNd3o6uuukratm2b7GoAAA4TjYMaD2vqz3/+s3To0EFq164tDRs2FK8566yzpFOnTgc9b/369eZzevbZZw9LvbyEewcgcWhMAwcwbtw4mT17doXjH374obmh2bFjh/U6fPXVV+a1li1bZv21gEQKOmnWCoD4ffrpp6Yhddxxx8mUKVNk8uTJya6SL3HvgFQTTOFY741aAiLyv//7v3LXXXe5JiDee++9hy0g6mtVFhD1Zmj16tXW6wAA8D6dXRYKheT3v/+9aVRfdtllya6SL3HvAKQO1kzDM+rUqZPsKriOTtMD3CokAQlZ6LMNiZPwawKpYOvWrebPRE7v3rNnj9StWzdh14N93DvAC/E+5JFYz8g0jE2bNsk111wjLVu2lMzMTDnmmGPkhhtukH379lX5nPfff18uvfRSad26tXlOTk6OjBgxwowgR9u8ebMMGTJEjj76aHPeUUcdJRdddJFZzxT2ySefSF5enjRp0kSOOOII8/pXX331QddM16Te6tFHH5XevXvLkUceaV4vNzdXXnrppQqvt3v3bnnuuefM/2vRnnytw//8z/+Yc/T1wj+Lfj/PP/+8uaZeu3HjxvLrX/9aSkpKKl339d///lfOPvtsczPSqlUrefjhh2NGEU455RTz//oZhl8rvAassnVPWuff/e535u9DP5P27dub9+s4sV9Kep1hw4aZ3nOth5570kknydy5cw/42YXrpc//y1/+Ynq+td4NGjSQSy65RHbu3CllZWVy6623SrNmzaR+/fqm7nos2vTp0+Wcc84x5+hrd+zYUZ566qkKr6Xv7xe/+IX84x//kG7duplOFT335ZdfPmg9AcDLPvjgAxMD9HtPp2Y//fTTVZ57sLij36Vjxowx/9+0adMKMfXJJ580MUC/jzWm3nTTTRVGUMNxa8mSJXLGGWeYuHXHHXdE1idrrJk4caIce+yx5mfnnXeeqYPGn7Fjx5r7AK2f3gN8++23Mdd+9dVX5YILLojEc32/+pxgsPLdZrUOGsfD9wyTJk2q9lR3jVX6Genn2r17d3nttdeq9VzuHbh3AMpjZBpmKlCPHj1M0Pztb39rEpNoI1UDhPY4Z2RkVPq8v/71r+bn2njVwLJo0SL54x//KF9++aX5WdivfvUrWblypdx8883my017xt966y3ZuHFj5LEGXA3uI0eOND3mGlwO9oVX03orneJ24YUXyhVXXGEa3jNnzjQdA6+//roJ5uEkLddee615Db2+0uBer149+eyzz+TFF1+Uxx9/3HQAKK2/euCBB+Tuu+820+f0+du2bTOfi954/Otf/4oZEfjuu+/k5z//ufzyl78052vdb7/9duncubP0799fTjzxRLnvvvtk9OjRpg59+vQxz9NgXhkNevq+3nnnHdPJoAFk3rx5JoDrZ6P1LX+jpp/zjTfeaALaH/7wB/P3pX83+nd6MEVFRSbo69/bmjVrzPvUHu+0tDTz3vTm4aOPPjIBXG8e9H2EafDTAKz1rVWrlvz973839dApiHoTF+3zzz+XQYMGyfXXXy8FBQUmmOrflwbvfv36HbSeSA6yeQM1t3z58khs1O/SH374wTSGmzdvXuHc6sSdCRMmyJ/+9Cd55ZVXzPevNla6dOlinq/X18ZN3759TUzXKcB6zuLFi+Wf//xnzEjmN998Y+KTNvR+85vfxNTnhRdeMDFV4702lrWBp3XSxo82pDS+hWPFbbfdJtOmTYs8V+OE1qmwsND8+fbbb5uYUVpaKo888kjM+9X4cv7555trDx482DTOtN4a98t3xEfTe5HTTjvNNOI0bmk81+cOHDhQ/va3v8nFF198wL8T7h1+xL0DygumcDZv/QeEFJefn++kpaU5ixcvrvCzUChk/nznnXe0a9L8GbZnz54K5xcVFTmBQMDZsGGDefzdd9+Z5z3yyCNVvv4rr7xizqns9aPpOWPGjImr3lUpX/d9+/Y5nTp1cs4555yY4/Xq1XMKCgoqPF/fj9Zn3bp1McfXr1/vpKenOw888EDM8eXLlzu1atWKOX7mmWeaa/zpT3+KHCsrK3NatGjh/OpXv4oc0/en502fPr1CPbRubdq0iTyePXu2Off++++POe+SSy4xfy9r1qyJHNPzMjIyYo79+9//Nsf/+Mc/OgcS/n3Qz0w/u7DBgweb1+nfv3/M+b169YqpZ1W/P3l5ec6xxx4bc0yfp6/1t7/9LXJs586dzlFHHeWcfPLJB6wnkkP/fvTv7JV/n+D8Y22HhBe9rl5fXwfwq4EDBzp16tSJxFP13//+18SY6Nu3eOKOxlB97rZt2yLHtm7damLBeeed5wSDwcjxJ554wpw7bdq0CnFr0qRJMa+lsVCPN23a1NmxY0fk+KhRo8zxrl27Ovv374+JFfqae/fuPWBMuO6665y6devGnBeuw2OPPRYTO7t16+Y0a9YsEpPCdYqOneeee67TuXPnmOvp/ULv3r2dE044wTkY7h24d8Dhi/eveCTWM807xWlPnk7VGTBggJnqVN6Btt/QXsXo6UHbt283vZ76Xau9qOFztKdYe6S1t7Ey4d5W7dndv3+/9XqXr7vWS6cXac/t0qVL5VBoT63WTXuK9fMIlxYtWsgJJ5xgen2jae+79uyH6Welvdlr166t0evPmTNH0tPT5ZZbbok5rlO39O/lzTffjDmuoxDaYx6moxRZWVnVfv38/PyYEYuePXua1yk/MqDHdaqajqxU9negn79+TmeeeaZ5bX0cTaf9RY8YaB31tfX3TJcRAICf6NRmHRnUEVNdShWmI466JOpQ4k558+fPN6OsOr1WRwbDhg4dar5r33jjjZjzdWqtTr+tjI76ZWdnx3z3K41zOooYfVxfU0c9K4sJ33//vXkPGpd1pplOzY6m17ruuutiYqc+1pluOv27MjpSrqPd+jmFr69FR9r1M9VRzOj6VIZ7hx9x7wD8H6Z5pzidRqRTqKqzZ2N5Op1Hp97oWqPyDeXwF5oG3Yceesh8IetUsFNPPdWsYdEvMw0SSr8EdXqQTjHTqUS6HkhvIC6//HLz/ETXO9xwv//++02Wy+j1OIeyd6fSYKwBQYNfdZJ+6Pqx8q/ZqFEj+c9//lOj19+wYYMJHjrtKpregIV/Hi36Ji369avq+Civ/PPDN1G65qr8cb1R0N+L8BQwnTqoUxYXLlxobpai6XnRN2THH398hc+pXbt25k9dEhD+XYIbE5IkfpqWjWsCbqIxTvOPVBZLdC2rNn5qGnfKC8cFvW40baDp2ufycUOnSFe1jCqemKCiY41OwdYdO7TBq/E9WmWNJJ02XVVM0HuN8nQ6sX5OOpVaS2W0Ma7vryrcO/yIewccjngf8kispzGNGvea63oT7enVdTq6XlkDm/bqamIL/fIL095uHUHWkWTtadcgputlNGCefPLJ5otO1/vo+hhd+6LnaO/kY489Zo5pD2wiaeI0XWuj65A04YomRNNApWtpZsyYcUjX1vet70d7cbWXt7zy76Wyc1T5hB+2HOrrV/X8g133iy++kHPPPdf83owfP94EUL050xtE7VCJ/v0BACQu7hyq6JHBRMUEzX2iHes6cqhrfXXUUxNG6Yiv3mMkIiaEr6FrtcuP7kc3vqrCvUPiXp97B/gJjekUp4kvNHitWLEi7sQomkhDs1XqKHOYJharjAZGHZ3Woj2wmtxCG8uauTJMe5K1aBIODUya4EOTe2gijkTVW2mSEQ3S2miPHvnWgFheVb3NVR3X96lf+powI9z7eaji6fFu06aNmbKnU9iie5jDU+T0526gnSbaq6+zGqJ7qKuajhgeUYj+LPT3T5XPSAr30G0ygmyNBcRNY5w2WjVelld+f+BDjTvhuKDX1ZHoMJ2GvW7dOjOl1zZdCqbTrXW6szZWw/T1q0pAqsvLokenDxYTwu9NG8A1eU/cOyQf9w6pFe9DHon1rJlOcbo+SqdU6xeUbk9V3V7GcO9h9M/1/zXTZTSdgrN3794KQUO/rMNTpHRaUPnX0ca2Kr8lwqHWO1x3/WKN3m5Dp/voyHl5GqjLbw0SPq7K/0wza+r1dcp6+TroY71ZiFdVr1UZzW6q7+uJJ56IOa49tvqeNcunG1T2+6PTsyq7KQnfOGkG2jCdAqhZafX3hGlaAPxGvyN19FTjki6pClu1apVpzCUy7mjDUkf3NCNz9POnTp1qvpfDWaoPd0zQxryOAFdG19BGbxOm5+pj7YTQraUqo1sp6TIyPe/rr7+udGr9werIvUNyce8AN2JkGjJu3DizD59OsdItFHSNjAYa3d5Ktz+I3o4hTKfYaKNYp0vp1G4dJdZe2/LrZbQHUKfkaFIN3d9Pk4boF9uWLVvMthpKR7c1YGqSCL2m9oxOmTLFXFO/4BNZb6U3Bjo9SLeV0HXZukZK98XU6V3l1xtpUNbeWj1f1xNpr7EmxAgH6zvvvNO8D+3p1qnsWn9dTzVq1CgTZLXBrx0H2ruu71vrqZ9ZPPSa+l50D029lgZIrYPWpTytg+47qfXS1+/atav5jHT/Tp1uH50wJJl0uxe9edP6atKYXbt2mb9zvdmp7CZHe+p1uw7dpkXX3ut2Kvo7VFUAhTsEnTRTEn9db/RWA4dCG1a6hY8muNKtf7QBqVsI6bZA0bHqUOOONkD1ufp6Ghd1KrOOUmtc1r2KoxNd2aLJS3XNrW5fpEmwtAGnW0xV1TGu8Vjzsej71fgwa9Yss4558uTJB1wjrrH+9NNPN1tIaYI1Ha3WWKLrb3Vbz3//+99VPpd7h+Tj3iG14n3QI7GexjRMso2PP/7YrGXWPSK1506PaU9k3bp1K32OBgAdFdagp+ufdeqTNoaHDRtmvoTDdD2L7gG5YMECExi1Ma0Ncd3XUZOOKW0M6x7VOqVbv+Q0eYRmpdS6VPalfyj1Vrrfpfa4P/jggyZI6GuEg3L5gKiBUIOYJkXRZDAa6DUY6Q3G2LFjTZDSmx1dp6NBT4OV7puoX+Dao6s3J+HPQYOA3qTESz9r7XDQIKt7JeoNlQaCyj4bHbHX6U+aGE5vLvQ8ncqke3TqFHu30EQ3uk5eP1e9QdAeYt0jVG/qKtsjVJOy6E2k7nmpN3n63vX9VbXuDQC8TjMk6yi07rus3+madEpjijYayseqQ407uq+vfv/qyOSIESOkcePGJvZpp/XBEpglgiaX0uReGqc0LmjDWhvx2hlf2fe8/lzjou5nrY0pbShp3bWBfCDaqa+z2fQz0j2MdcRXG2KavyV6L+PKcO+QfNw7wI0Cuj9WsisBAFXRgK5Z2/VGC96gHVvaKTZjWSep26DyhDKHYs/3Qbm82wozvU9nsAAAEI17B+/H+z01iPU6W0Q7gXTrMx3c084UHaCrjC77ePfddysc11mx5bcEPBBGpgEAVgSdgCk2rgsAAPwb74NxXk9nHehMHp35oTNBJkyYYGYh6KwEnYFSniY81HwLYTpTRRvgl156aVyvSwIyAAAAAIArR79Lo0pVyYl1eYUu9RgyZIhZ0qGNal32qWvlK6PLWXSpQLjojkR6Po1pAIAr6DYZtgoAAHCHoMVYr7kDdCp5uGiupvJ0hHnJkiUx295pLgB9rAkGq0NzImhiwOgt96qDad4AXE2TuwAAAFQX9w7+UVJSErNmOnqf97Dt27eb7d00GWE0fRzeL/1ANBHyihUrTIM6XjSmAQBWhJw0UxJ/XfJmAgDg53gf+inWa0PadrJRbUTrlnlVJSvzbWNatxTQDdl1/zzdkxAAEB/d0EH3dte9UHVKFOA2xHoAOHR+jvdNmjSR9PR0s8VuNH2s66EPZPfu3WZ73vvuu69Gr+3pxrQGV51HDwA49GlUuo9tItla3xwURqZTCbEeAFIv3gfjiPUZGRmSm5srCxYskIEDB0Y6YvXxsGHDDvjcv/71ryapme5tn3KNae2lVtfNO18y6tUWN1txbsX5/W6Vdow3blqCn60TL0jPii+RQTKFdu0RL3BCHmpMhYLiZj/IfvlA5kS+TwG3Cf9ubljaVrLqu3s05eJ2nZNdBeCg0k88QbwguOrzZFfBV/we7wsLC6WgoEC6d+9upmvr1lg66qzZvVV+fr60atWqQgIzneKtDfAjjzwy9RrT4ele2pDOrO/uxnStgLvrFy0t3RsN/4BHPtP0QIZ4RSiwX7zACXioMR1w981/uOPXxvTZkKU9ofW6SB3h301tSGc1cPe/Jy/FeqSudO7zUpPH4n0ozvMHDRok27Ztk9GjR8vmzZulW7duMnfu3EhSso0bN1aY3q57UH/wwQfyj3/8o8b19HRjGgDgXiFJM8XGdQEAgH/jfagG19Mp3VVN6y4uLq5wrH379mYt+aHgjgQAAAAAgDgxMg0AsCLopJli47oAAMC/8T7okVjvjVoCAAAAAOAijEwDAKwIScAUG9cFAAD+jfchj8R6RqYBAAAAAIgTI9MAACtYMw0AgP8FWTMNAAAAAACqi5FpAIAVQUkzxcZ1AQCAf+N90COxnsY0AMCKkBMwxcZ1AQCAf+N9yCOx3htNfgAAAAAAXISRaQCAFSFL07z1ugAAwL/xPuSRWO+NWgIAAAAA4CKMTAMArAg5aabYuC4AAPBvvA95JNZ7o5YAAAAAALiIKxrTEydOlLZt20qdOnWkZ8+esmjRomRXCQBwiIISsFbgPcR6APCnYArH+qQ3pmfNmiWFhYUyZswYWbp0qXTt2lXy8vJk69atya4aAABIAGI9AMCPkt6YHj9+vAwdOlSGDBkiHTt2lEmTJkndunVl2rRpya4aACABa6hsFHgLsR4A/CuUwrE+qbXct2+fLFmyRPr27ft/FUpLM48XLlxY4fyysjIpLS2NKQAAwL2I9QAAv0pqY3r79u0SDAalefPmMcf18ebNmyucX1RUJNnZ2ZGSk5NzGGsLAIhH0No6KvvrdSdMmCDt27eXI444wsSaESNGyN69e2v8WaQyYj0A+FvQSrz3Bm+Mn/9k1KhRsnPnzkgpKSlJdpUAAC6f5h3vet0ZM2bIyJEjzfmrVq2SqVOnmmvccccdCfpkcCDEegDwlpALYn1K7jPdpEkTSU9Ply1btsQc18ctWrSocH5mZqYpAACUn/5bVYyIXq+rdL3uG2+8YdbraqO5vA8//FBOO+00ufzyy81jHdEePHiwfPzxx9bei58R6wEAfpXUJn9GRobk5ubKggULIsdCoZB53KtXr2RWDQBwiIJOmrWidPpv9HRgnR58qOt1Ve/evc1zwlPB165dK3PmzJHzzz/f2mflZ8R6APC3oMVY73ZJHZlWOvWuoKBAunfvLj169DDr1Hbv3h0ZQQAAoDI6/TcrKyvyuLLRzAOt1/30008rva6OSOvzTj/9dHEcR3744Qe5/vrrmeZ9CIj1AAA/SnpjetCgQbJt2zYZPXq0SUTSrVs3mTt3boUbHwCAtzgSkJAErFxXaUM6ujGdKMXFxTJu3Dh58sknTbKyNWvWyPDhw2Xs2LFy9913J/z1UgGxHgD8y7EQ78Ox3u2S3phWw4YNMwUAgGSu11XaYL7yyivl2muvNY87d+5sRlF/+9vfyp133mmmiSN+xHoAgN9wRwAA8OSaaVvrdffs2VOhwawNcqXTvgEAwP9JdqyXVB+ZBgAgWet18/PzpVWrVpEEZgMGDDAZwE8++eTING8drdbj4UY1AAAAjWkAgBUhJ2CKjesmcr3uxo0bY0ai77rrLgkEAubPTZs2SdOmTU1D+oEHHkj4ewEAwOtCFuK9jfsHG2hMAwCsCEqaKTaum8j1uppwLFqtWrVkzJgxpgAAgMMf74MeWY3sjVoCAAAAAOAijEwDAHw9zRsAANgTSuFp3oxMAwAAAAAQJ0amAQBWhCTNFBvXBQAA/o33IY/Eem/UEgAAAAAAF2FkGgBgRdAJmGLjugAAwL/xPuiRWM/INAAAAAAAcWJkGgBgBdm8AQDwv1AKZ/OmMQ0AsMJx0iTkpFm5LgAA8G+8dzwS633RmF7Zv77UCmSIm7V5/wfxii8vKhUvSM/OEi8I7dotXhHIcPe/o4hgULzD3V+zAQ1WZcmuBXBwF7frLLUCtcXN5n21TLwir2W3ZFcBSRJcuTrZVQB8w913eQAAzwpKwBQb1wUAAP6N90GPxHpvjJ8DAAAAAOAijEwDAKwIOXYSiOh1AQCAf+N9yCOxnpFpAAAAAADixMg0AMCKkKVs3jauCQAA3BPvQx6J9d6oJQAAAAAALsLINADAipAETLFxXQAA4N94H/JIrGdkGgBgRdAJWCsAAMAdgi6J9RMnTpS2bdtKnTp1pGfPnrJo0aIDnr9jxw656aab5KijjpLMzExp166dzJkzJ67XZGQaAAAAAOBZs2bNksLCQpk0aZJpSE+YMEHy8vJk9erV0qxZswrn79u3T/r162d+9tJLL0mrVq1kw4YN0rBhw7hel8Y0AMAKEpABAOB/IRckIBs/frwMHTpUhgwZYh5ro/qNN96QadOmyciRIyucr8e//fZb+fDDD6V27drmmI5qx4s7EgAAAACA65SWlsaUsrKySkeZlyxZIn379o0cS0tLM48XLlxY6XVfe+016dWrl5nm3bx5c+nUqZOMGzdOgsFgXPWjMQ0AsJeQxLFQPJKUBACAVBASe7E+JydHsrOzI6WoqKjC62/fvt00grVRHE0fb968udI6r1271kzv1ufpOum7775bHnvsMbn//vvjeu9M8wYAAAAAuE5JSYlkZWVFHmuisEQIhUJmvfTkyZMlPT1dcnNzZdOmTfLII4/ImDFjqn0dGtMAACscS1tj6XUBAIB/473z0/W0IR3dmK5MkyZNTIN4y5YtMcf1cYsWLSp9jmbw1rXS+rywE0880Yxk67TxjIyMatWTad4AAAAAAE/KyMgwI8sLFiyIGXnWx7ouujKnnXaarFmzxpwX9tlnn5lGdnUb0orGNADACivrpX8qAADAHUIuiPW6LdaUKVPkueeek1WrVskNN9wgu3fvjmT3zs/Pl1GjRkXO159rNu/hw4ebRrRm/tYEZJqQLB5M8wYAWMHWWAAA+F/IBVtjDRo0SLZt2yajR482U7W7desmc+fOjSQl27hxo8nwHaaJzebNmycjRoyQLl26mH2mtWF9++23x/W6Sb0jee+992TAgAHSsmVLCQQCMnv27GRWBwAAJBixHgBwOAwbNkw2bNhgts/6+OOPpWfPnpGfFRcXy7PPPhtzvk4B/+ijj2Tv3r3yxRdfyB133BGzhtr1jWkdeu/atatMnDgxmdUAAFjANG8oYj0A+FsohWN9Uqd59+/f3xQAAOBPxHoAgF95as20DtlrCSstLU1qfQAAVQtZ2hrLxjXhHsR6APCWkIV475VY76ksLkVFRZKdnR0punAcAAD4B7EeAOAVnmpMazrznTt3RkpJSUmyqwQAqAJrplETxHoA8JZQCsd6T03zzszMNAUAAPgTsR4A4BWeakwDALzDVs+yV3qrAQBIBSEL8d4rsT6pjeldu3bJmjVrIo/XrVsny5Ytk8aNG0vr1q2TWTUAwCGiMQ1FrAcAfwvRmE6OTz75RM4+++zI48LCQvNnQUFBhU21AQCA9xDrAQB+ldTG9FlnnSWO4ySzCgAASxiZhiLWA4C/hVJ4ZNpT2bwBAAAAAHADEpABAKzQsciQJL5nmTFOAAD8He8d8QZGpgEAAAAAiBMj0wAAK1gzDQCA/4VYMw0AAAAAAKqLkWkAgBWMTAMA4H+hFB6ZpjENALCCxjQAAP4XSuHGNNO8AQAAAACIEyPTAAArGJkGAMD/QoxMAwAAAACA6mJkGgBgheMETLFxXQAA4N9473gk1jMyDQAAAABAnBiZBgBYEZKAKTauCwAA/BvvQx6J9YxMAwAAAACQkiPToZBIICRutv7UfeIVU9a/JF4wtE0f8YSAd/qsnP3e+T1FYjjOfmvXJps3Ein9xBMkPT1T3CyvpXjGvK+WiRfkteyW7CoAOIhQCmfz9kdjGgDgOiQgAwDA/xwSkAEAAAAAgOpiZBoAYAXTvAEA8L9QCk/zZmQaAAAAAIA4MTINALCCNdMAAPifw5ppAAAAAABQXYxMAwCs0F5lG2uevNJbDQBAKnAsxHuvxHpGpgEAAAAAiBMj0wAAKxzTs2znugAAwL/x3hFvYGQaAAAAAIA4MTINALAiJAHzn43rAgAA/8b7kEdiPY1pAIAVbI0FAID/OWyNBQAAAAAAqouRaQCAFbpNRsBCz7KN7bYAAIB74n3II7GekWkAAAAAAOLEyDQAwArdJsPK1lhe2S8DAIAU4FiI916J9YxMAwAAAADgpcZ0UVGRnHLKKdKgQQNp1qyZDBw4UFavXp3MKgEAEpzd00aBdxDrAcDfnBSO9UltTL/77rty0003yUcffSRvvfWW7N+/X8477zzZvXt3MqsFAAAShFgPAPCrpK6Znjt3bszjZ5991vRaL1myRM4444wK55eVlZkSVlpaeljqCQCIH/tMQxHrAcDfHPaZdoedO3eaPxs3blzlVLHs7OxIycnJOcw1BADEs62FrQLvItYDgL+EUjjWu6YxHQqF5NZbb5XTTjtNOnXqVOk5o0aNMkE4XEpKSg57PQEAQM0Q6wEAfuKaxrSup1qxYoXMnDmzynMyMzMlKysrpgAA3L1Vho0CbyLWA4D/OC6J9RMnTpS2bdtKnTp1pGfPnrJo0aIqz9UlR4FAIKbo8zzZmB42bJi8/vrr8s4778jRRx+d7OoAAIAEI9YDAGyZNWuWFBYWypgxY2Tp0qXStWtXycvLk61bt1b5HO2s/frrryNlw4YN3mpMO45jgusrr7wib7/9thxzzDHJrA4AIIF+7Fm2sV1Gst8Z4kGsBwB/c6zE+/jqMH78eBk6dKgMGTJEOnbsKJMmTZK6devKtGnTqnyOjka3aNEiUpo3b+6txrRO93r++edlxowZZv/JzZs3m/K///u/yawWAABIEGI9AKCmdEeH6BK920PYvn37zA4Rffv2jRxLS0szjxcuXFjltXft2iVt2rQxiS4vuugiWblypbca00899ZRJLnLWWWfJUUcdFSk6TA8A8DY7o9J2ttuCPcR6APA3x2Ks14Zu9A4PuuNDedu3b5dgMFhhZFkfa+dtZdq3b29GrV999VXT4asJMnv37i1ffvmld/aZ1qlfAADAv4j1AICa0h0dohNRapLKROjVq5cpYdqQPvHEE+Xpp5+WsWPHeqMxDQDwL21C2WhG0TQDAMDf8d756c/q7OrQpEkTSU9Ply1btsQc18e6Fro6ateuLSeffLKsWbPGe9m8AQD+46Zp3vFsl6F27Nhh1vrqdGTtBW/Xrp3MmTPnED4NAAD8yUlyrM/IyJDc3FxZsGBB5JhO29bH0aPPB6LTxJcvX27ifjwYmQYApMR2GZrZUxvSEyZMMNtlrF69Wpo1a1ZpIpN+/fqZn7300kvSqlUrs11Gw4YNk1J/AABwYBrnCwoKpHv37tKjRw8T63fv3m2ye6v8/HwTz8Nrru+77z459dRT5fjjjzcd6I888oiJ9ddee63Eg8Y0AMDX87yjt8tQ2qh+4403TOKRkSNHVjhfj3/77bfy4YcfmmlfSke1AQDAYZ7nXU2DBg2Sbdu2yejRo03SsW7dusncuXMjSck2btxoMnyHfffdd+beQM9t1KiRGdnWuK/basWDxjQAwJN0i4xoOh27fGKS8HYZo0aNqvZ2Ga+99pqZFqbTvDXLZ9OmTeXyyy+X22+/3azJAgAA7jNs2DBTKlNcXBzz+PHHHzflULFmGgBgh601VJa3y1i7dq2Z3q3P03XSd999tzz22GNy//33W/qgAADwMMderHc7RqYBAJ5ka7sMTVqi66UnT55sRqJ16temTZvMeqoxY8Yk5DUAAID30ZgGAFih2wvb2GI4fE1b22VoJk9dKx09pVv3ntSRbJ02rllDAQCAvXhv4/7BBqZ5AwB8qybbZZx22mlmn0k9L+yzzz4zjWwa0gAAIIzGNADA1/tM63YZU6ZMkeeee05WrVolN9xwQ4XtMqITlOnPNZv38OHDTSNaM3+PGzfOJCQDAACxHBfE+mRhmjcAwA5bCUTivGa822VoYrN58+bJiBEjpEuXLmZfSm1YazZvAABwGOK9Q2MaAADPbZehdAr4Rx99dBhqBgAAvIrGNADAkwnIAABA8jkpnIDMF41pZ98P4gTcPRUgPau+eMX1nc4XL+jz763iBf/sdaR4RWjPHvGCtARtgXRY1K4tbpbm7BP5Ptm1AA4uuOpzCQTc/e8p/aT24hXn9/NGXed9NUu84Px+g8QrgitXJ7sKgG/4ojENAHAh7VW20bPskd5qAABSgmMhNnsk1pPNGwAAAACAODEyDQCwwtbWFl7ZLgMAgFTgWIj3Xon1jEwDAAAAABAnRqYBAPZ4ZM0TAAA4BI6kJBrTAAArmOYNAID/OUzzBgAAAAAA1cXINADADrbGAgDA/xy2xgIAAAAAANXEyDQAwBJd72RjzZM31lEBAJAaAhZiszdiPSPTAAAAAADEiZFpAIAdrJkGAMD/HNZMAwAAAACAamJkGgBgByPTAAD4n5O6I9M0pgEAdjiBH4uN6wIAAP/Ge8cbsZ5p3gAAAAAAxImRaQCAFY7zY7FxXQAA4N9473gk1id1ZPqpp56SLl26SFZWlim9evWSN998M5lVAgAACUSsBwD4VVIb00cffbQ8+OCDsmTJEvnkk0/knHPOkYsuukhWrlyZzGoBABKZkMRGgWcQ6wHA55zUjfVJneY9YMCAmMcPPPCA6cH+6KOP5KSTTqpwfllZmSlhpaWlh6WeAACgZoj1AAC/ck0CsmAwKDNnzpTdu3ebKWCVKSoqkuzs7EjJyck57PUEAMSZ3dNGgScR6wHAh5zUjfVJb0wvX75c6tevL5mZmXL99dfLK6+8Ih07dqz03FGjRsnOnTsjpaSk5LDXFwAAxIdYDwDwo6Rn827fvr0sW7bMBMyXXnpJCgoK5N133600yGoQ1gIAcL+A82OxcV14C7EeAPwrYCHeeyXWJ70xnZGRIccff7z5/9zcXFm8eLH8/ve/l6effjrZVQMAHApbCUQ8EmDxf4j1AOBjjoXY7JFYn/Rp3uWFQqGYxCMAAMBfiPUAAD9I6si0rovq37+/tG7dWr7//nuZMWOGFBcXy7x585JZLQBAIthKIOKRpCT4EbEeAHzOsRDvPRLrk9qY3rp1q+Tn58vXX39tMnZ26dLFBNd+/fols1oAACBBiPUAAL9KamN66tSpyXx5AIBNrJkGsR4A/M9hzTQAAAAAAPBKNm8AgE8xMg0AgP85jEwDAAAAAIBqYmQaAGAHI9MAAPifk7oj0zSmAQB2sDUWAAD+56Tu1lg1muY9ffp02bNnT+JrAwAAXIN4DwBAghvTI0eOlBYtWsg111wjH374YU0uAQDwuYBjr+DwIN4DAA4mkMKxvkaN6U2bNslzzz0n27dvl7POOks6dOggDz30kGzevDnxNQQAAElBvAcAIMGN6Vq1asnFF18sr776qpSUlMjQoUPlhRdekNatW8uFF15ojodCoZpcGgDgt4QkNgoOC+I9AOCgnNSN9Ye8NVbz5s3l9NNPl169eklaWposX75cCgoK5LjjjpPi4uLE1BIAACQV8R4AgAQ1prds2SKPPvqonHTSSWbqV2lpqbz++uuybt06My3ssssuM0EWAAB4F/EeAOAFEydOlLZt20qdOnWkZ8+esmjRomo9b+bMmRIIBGTgwIGHpzE9YMAAycnJkWeffdZM+dJg+uKLL0rfvn3Nz+vVqye/+93vzJQwAADgTcR7AIAXzJo1SwoLC2XMmDGydOlS6dq1q+Tl5cnWrVsP+Lz169fLbbfdJn369Dl8+0w3a9ZM3n33XTPVqypNmzY1vdYAgNSkO0TayMbpjZ0n/YF4DwBIRrwPxHn++PHjTafvkCFDzONJkybJG2+8IdOmTTM7U1QmGAzKFVdcIffee6+8//77smPHjsPTmJ46dWrk//fu3WuG0svTofI2bdrI4eAEg+IEDnn5t1XBHTvFM9LSxQve73qEeMFfSuaLV1yW01u8ILRvv3jG3r3iZiHH4mfpBH4sNq6Lw8JN8T79xBMkPT1T3Cy4crV4RfpJ7cULzu83SLxgzluzxCvyWnZLdhWAatOlRdEyMzNNibZv3z5ZsmSJjBo1KnJMc3voLKqFCxdWee377rvPdBrr9o/amK6JGrVANXPn2LFjpVWrVlK/fn1Zu3atOX733XfHBF4AAOBdxHsAQLU7z50EFxGz1Cg7OztSioqKKry8bt+oo8yaKDOaPq5qK8cPPvjAxLEpU6Yc0luvUWP6/vvvN+unHn74YcnIyIgc79SpkzzzzDOHVCEAgE+wNZbnEe8BAAfl2Iv1mpNj586dkRI9+lxT33//vVx55ZWmId2kSZNDulaNpnn/6U9/ksmTJ8u5554r119/feS4LvT+9NNPD6lCAADAHYj3AIBkysrKMuVAtEGcnp5udp+Ipo9btGhR4fwvvvjCJB7TJJvRM7FUrVq1ZPXq1WbbR2sj05rN8/jjj69wXCuxf7+H1jICAOxhZNrziPcAgINykhvrdeZUbm6uLFiwICZO6ePKEmh26NBBli9fLsuWLYuUCy+8UM4++2zz/zq13OrIdMeOHc0i7fIJR1566SXp1o2kBgAA+AHxHgDgBYWFhVJQUCDdu3eXHj16yIQJE2T37t2R7N75+fkm/4euudZkmrpcKVrDhg3Nn+WPW2lMjx492lRWe6y11f/yyy+b4fDnnntO/va3v9XkkgAAn9FtMqxsjcXI9GFDvAcAJCPeB+K83qBBg2Tbtm0mbmnSMe3wnTt3biQp2caNG02G70SL64qPP/64+fOiiy6Sv//97zJ//nypV6+eqfSqVatMT/WDDz6Y8EoCAIDDh3gPAPCaYcOGyYYNG6SsrEw+/vhj6dmzZ+RnxcXFJqFmVfRns2fPjvs14xqZvuOOO+TII480w+R9+vSRt956K/KzXbt2SV5ennzzzTdxVwIA4EO21jczMm0d8R4AkNR474gnxDUy/ec//1muu+46ee2112KO63z0/v37mz2+3n777UTXEQAAHEbEewAAEjwyfckll8iOHTtk8ODB8sYbb8hZZ51lAuvPf/5zMzddh89btmwZzyUBAH7FyLRnEe8BANXmpO7IdNwJyK699lr59ttvzTqqV1991ayf+uqrr+Tdd981GdIAAFAkIPM24j0AwCsJyJKlRtm8/9//+38mwJ577rnStm1b00N99NFHJ752AAAgaYj3AAAkqDH9y1/+MuZx7dq1pUmTJjJ8+PCY47p1BgAgxTmBH4uN68Iq4j0AIKnx3gn4rzGdnZ0d81jXUgEAAH8h3gMAkODG9PTp0+M5HQCQykhA5lnEewBAtTmpm4Asrq2xAAAAAABADROQAQBwMGTzBgDA/wIpnM3bNSPTDz74oAQCAbn11luTXRUAAGAJ8R4A4BeuGJlevHixPP3009KlS5dkVwUAkCismUY5xHsA8CGHNdNJs2vXLrniiitkypQp0qhRo2RXBwCQKD9N+0p08UqARSziPQD4lJO6sT7pjembbrpJLrjgAunbt+9Bzy0rK5PS0tKYAgAA3K+68Z5YDwDwiqRO8545c6YsXbrUTPuqjqKiIrn33nut1wsAkABM80YN4j2xHgA8xmGa92FXUlIiw4cPlxdeeEHq1KlTreeMGjVKdu7cGSl6DQAA4F7xxntiPQDAK5I2Mr1kyRLZunWr/OxnP4scCwaD8t5778kTTzxhpnmlp6fHPCczM9MUAIAHMDKNGsR7Yj0AeIyTuiPTSWtMn3vuubJ8+fKYY0OGDJEOHTrI7bffXqEhDQAAvId4DwDwq6Q1phs0aCCdOnWKOVavXj058sgjKxwHAHhPJCOnhevCO4j3AOBvAQvx3iuxPunZvAEAAAAA8JqkZvMur7i4ONlVAAAAlhHvAQB+4KrGNADAR0hABgCA/zmpm4CMad4AAAAAAMSJkWkAgBUkIAMAwP8CJCADAAAAAADVxcg0AMAej/QsAwCAQ+BISmJkGgAAAACAODEyDQCwg2zeAAD4n0M2bwAAAAAAUE2MTAMArCCbNwAA/hdI4WzeNKYBAHYwzRsAAP9zmOYNAAAAAACqicY0AMDqtC8bJV4TJ06Utm3bSp06daRnz56yaNGiaj1v5syZEggEZODAgfG/KAAAKSDgklifDDSmAQC+NmvWLCksLJQxY8bI0qVLpWvXrpKXlydbt2494PPWr18vt912m/Tp0+ew1RUAAHgHjWkAgN01VDZKHMaPHy9Dhw6VIUOGSMeOHWXSpElSt25dmTZtWpXPCQaDcsUVV8i9994rxx577KF/FgAA+JWT/FifLP5IQOaERESLiwUC4q3P0wMcb/wru6z16eIVUze8K14wtF1f8YrQ3mCyq+BbpaWlMY8zMzNNibZv3z5ZsmSJjBo1KnIsLS1N+vbtKwsXLqzy2vfdd580a9ZMrrnmGnn//fct1B7xCq76XAKB2smuhm8EV65OdhV85fx+g8Qr5n01S7wgr2W3ZFcBOChGpgEAnhyZzsnJkezs7EgpKiqqUIXt27ebUebmzZvHHNfHmzdvrrTaH3zwgUydOlWmTJli53MBAMBPHEamAQDwlJKSEsnKyoo8Lj8qXRPff/+9XHnllaYh3aRJk0O+HgAA8C8a0wAAK2xl4wxfUxvS0Y3pymiDOD09XbZs2RJzXB+3aNGiwvlffPGFSTw2YMCAyLFQ6MelL7Vq1ZLVq1fLcccdl5g3AgCADwQsxHuyeQMAUpsLEpBlZGRIbm6uLFiwIKZxrI979epV4fwOHTrI8uXLZdmyZZFy4YUXytlnn23+X6eWAwCAKEzzBgDAn3RbrIKCAunevbv06NFDJkyYILt37zbZvVV+fr60atXKrLnWfag7deoU8/yGDRuaP8sfBwAAqY3GNADADls9y3Fec9CgQbJt2zYZPXq0STrWrVs3mTt3biQp2caNG02GbwAA4JJ474gn0JgGAPjesGHDTKlMcXHxAZ/77LPPWqoVAADwMhrTAABPJiADAADJFyABGQAAAAAAqC5GpgEAvl4zDQAALHJSd800I9MAAAAAAMSJxjQAwOoaKhsFAAC4Q8AlsX7ixInStm1bs81lz549ZdGiRVWe+/LLL5stM3X7y3r16pmdPv785z/H/Zo0pgEAdqd92SgAAMAdnOTH+lmzZklhYaGMGTNGli5dKl27dpW8vDzZunVrpec3btxY7rzzTlm4cKH85z//kSFDhpgyb968uF6XxjQAAAAAwHVKS0tjSllZWaXnjR8/XoYOHWoaxB07dpRJkyZJ3bp1Zdq0aZWef9ZZZ8nFF18sJ554ohx33HEyfPhw6dKli3zwwQdx1Y/GNADADkamAQDwP8derM/JyZHs7OxIKSoqqvDy+/btkyVLlkjfvn0jx9LS0sxjHXk+aPUdRxYsWCCrV6+WM844I663TjZvAAAAAIDrlJSUSFZWVuRxZmZmhXO2b98uwWBQmjdvHnNcH3/66adVXnvnzp3SqlUrM9qdnp4uTz75pPTr1887I9P33HOPBAKBmNKhQ4dkVgkAkCABiwXeQawHAH8LWIz12pCOLpU1pmuqQYMGsmzZMlm8eLE88MADZs11cXGxt0amTzrpJJk/f37kca1aSa8SAABIIGI9AMCWJk2amJHlLVu2xBzXxy1atKjyeToV/Pjjjzf/r9m8V61aZaaR63rq6kp6NNOAeqA3CQDwKFvrm1kz7TnEegDwMcdCbI7jehkZGZKbm2vWPQ8cONAcC4VC5vGwYcOqfR19TlUJzlzbmP7888+lZcuWZj+wXr16md6A1q1bV3quvrnoN6gZ3QAAgLsR6wEANukU7YKCArN3dI8ePWTChAmye/duk91b5efnm/XR4QRm+qeeq5m8NebMmTPH7DP91FNPeacxrZtpP/vss9K+fXv5+uuv5d5775U+ffrIihUrzBz28vRN6zkAAPcLOD8WG9eFdxDrAcDfAhbifbzXGzRokGzbtk1Gjx4tmzdvNtO2586dG0lKtnHjRjOtO0wb2jfeeKN8+eWXcsQRR5hcHs8//7y5Tnz11FzgLrFjxw5p06aN2SfsmmuuqVZvtaZLPyswUGoFah/m2iLp3POre2Bp6eIVU9e/K14wtN3/bX3gdqG9e8XNfnD2S7G8ajJaRmfLPBT63azbV5x03ThJz6wjiRYs2ysrn74joXWGB2K9XESsh2uln9RevGLOW7PEC/Jadkt2FXzFa/E+6JFYn/Rp3tEaNmwo7dq1kzVr1lT6c83elsgMbgAA4PAi1gMA/CKpW2OVt2vXLvniiy/kqKOOSnZVAACJTEqSyAJPI9YDgA85qRnrk9qYvu222+Tdd9+V9evXy4cffigXX3yxSWs+ePDgZFYLAAAkCLEeAOBXSZ3mrQu+NZh+88030rRpUzn99NPlo48+Mv8PAPA2EpBBEesBwN8CLkhAlpKN6ZkzZybz5QEAgGXEegCAX7kqARkAwEdsrXvySG81AAApwbEQmz0S612VgAwAAAAAAC9gZBoAYAVrpgEA8L8Aa6YBAEgwpnkDAOB/DtO8AQAAAABANTEyDQCwgmneAAD4XyCFp3kzMg0AAAAAQJwYmQYA2MGaaQAA/M9hzTQAAAAAAKgmRqYBAHYwMg0AgP85jEwDAAAAAIBqYmQaAGAF2bwBAPC/ANm8AQAAAABAdTEyDQCwgzXTAAD4n5O6a6Z90ZgOZGRIIFA72dXwj5A3fnsDtb3x6xtoUF+84rozrxAvaFn8jXjFl73TxdWckEjIzqUDjmOKjesCbpR+UnvxiuDK1cmugq946fPMa9lNvGDeV8vEK7zymdoSsBDvvRLrmeYNAAAAAECcvDG0BwDwHqZ5AwDgf07qTvNmZBoAAAAAgDgxMg0AsIKtsQAA8L8AW2MBAAAAAIDqYmQaAGAHa6YBAPA/hzXTAAAAAACgmhiZBgBYwZppAAD8L5DCa6ZpTAMA7GCaNwAA/ucwzRsAAAAAAFQTI9MAACuY5g0AgP8FUniaNyPTAAAAAADEiZFpAIAdrJkGAMD/HNZMAwAAAACAamJkGgBgjVfWPAEAgJoLpGi8Z2QaAAAAAIA4MTINALDDcX4sNq4LAAD8G+8db8T6pI9Mb9q0SX7zm9/IkUceKUcccYR07txZPvnkk2RXCwCQoK0ybBR4C7EeAPwrkMKxPqkj0999952cdtppcvbZZ8ubb74pTZs2lc8//1waNWqUzGoBAIAEIdYDAPwqqY3phx56SHJycmT69OmRY8ccc0yV55eVlZkSVlpaar2OAIAaYmssEOsBwP8ctsZKitdee026d+8ul156qTRr1kxOPvlkmTJlSpXnFxUVSXZ2dqRocAYAAO5FrAcA+FVSG9Nr166Vp556Sk444QSZN2+e3HDDDXLLLbfIc889V+n5o0aNkp07d0ZKSUnJYa8zAKB6AiF7Bd5BrAcAfwukcKxP6jTvUChkeqvHjRtnHmtv9YoVK2TSpElSUFBQ4fzMzExTAACANxDrAQB+ldSR6aOOOko6duwYc+zEE0+UjRs3Jq1OAIAEr6GyUeAZxHoA8DkndWN9UhvTmt1z9erVMcc+++wzadOmTdLqBAAAEodYDwDwq6RO8x4xYoT07t3bTP267LLLZNGiRTJ58mRTAADeZmufSK/sPYkfEesBwN8CFuK9V2J9UkemTznlFHnllVfkxRdflE6dOsnYsWNlwoQJcsUVVySzWgCARHAcewWeQawHAJ9z3BHrJ06cKG3btpU6depIz549TedtVXRXiT59+kijRo1M6du37wHPd+XItPrFL35hCgAA8CdiPQDAplmzZklhYaFJbqkNae20zcvLM8uMdFvG8oqLi2Xw4MFm5pQ2vh966CE577zzZOXKldKqVStvjEwDAPw/7ctGAQAA7hBwQawfP368DB06VIYMGWKSXmqjum7dujJt2rRKz3/hhRfkxhtvlG7dukmHDh3kmWeeMbtPLFiwIK7XpTENAAAAAHCd0tLSmFJWVlbhnH379smSJUvMVO2wtLQ083jhwoXVep09e/bI/v37pXHjxnHVj8Y0AMAOtsYCAMD/HHuxPicnR7KzsyOlqKiowstv375dgsGgNG/ePOa4Pt68eXO13sLtt98uLVu2jGmQe2LNNAAAAAAA5ZWUlEhWVlbkcWZmpiTagw8+KDNnzjTrqHX9dDxoTAMArGBrLAAA/C9gcWssbUhHN6Yr06RJE0lPT5ctW7bEHNfHLVq0OOBzH330UdOYnj9/vnTp0iXuejLNGwAAAADgSRkZGZKbmxuTPCycTKxXr15VPu/hhx822zXOnTtXunfvXqPXZmQaAGCHrT2h2WcaAAB/x3snvuvptlgFBQWmUdyjRw+zNdbu3btNdm+Vn59vtrwKr7nWrbBGjx4tM2bMMHtTh9dW169f35TqojENALCCad4AAPhfwOI07+oaNGiQbNu2zTSQtWGsW17piHM4KdnGjRtNhu+wp556ymQBv+SSS2KuM2bMGLnnnnuq/bo0pgEAAAAAnjZs2DBTKqPJxaKtX78+Ia9JYxoAYIetbawYmQYAwN/x3hFPIAEZAAAAAABxYmQaAGAFa6YBAPC/gAvWTCcLI9MAAAAAAMSJkWkAgB0h58di47oAAMC/8T7kjVjvi8a0U1YmTiCU7GrgMHN+2C+esGdPsmvgO1+eKp4x76tl4mal34ekUbtk1wLwh+DK1cmuAnBQ6Se1Fy84v5836qnmfTVL3I54b4cvGtMAABcimzcAAP7npG42bxrTAAArApYSiOh1AQCAf+N9QLyBBGQAAAAAAMSJkWkAgB2O82OxcV0AAODfeO94I9YzMg0AAAAAQJxoTAMArND1U7ZKvCZOnCht27aVOnXqSM+ePWXRokVVnjtlyhTp06ePNGrUyJS+ffse8HwAAFJZwCWxPhloTAMAfG3WrFlSWFgoY8aMkaVLl0rXrl0lLy9Ptm7dWun5xcXFMnjwYHnnnXdk4cKFkpOTI+edd55s2rTpsNcdAAC4F41pAIDdrTJslDiMHz9ehg4dKkOGDJGOHTvKpEmTpG7dujJt2rRKz3/hhRfkxhtvlG7dukmHDh3kmWeekVAoJAsWLEjM5wIAgJ84yY/1yUJjGgDgSaWlpTGlrKyswjn79u2TJUuWmKnaYWlpaeaxjjpXx549e2T//v3SuHHjhNYfAAB4G41pAIAVAcexVpROv87Ozo6UoqKiCnXYvn27BINBad68ecxxfbx58+ZqvY/bb79dWrZsGdMgBwAAP7IZ692OrbEAAHaEfio2risiJSUlkpWVFTmcmZmZ8Jd68MEHZebMmWYdtSYvAwAAhyHeh8QTaEwDADxJG9LRjenKNGnSRNLT02XLli0xx/VxixYtDvjcRx991DSm58+fL126dElInQEAgH8wzRsA4Mlp3tWRkZEhubm5McnDwsnEevXqVeXzHn74YRk7dqzMnTtXunfvfsifBQAAfhVgmjcAAP6k22IVFBSYRnGPHj1kwoQJsnv3bpPdW+Xn50urVq0ia64feughGT16tMyYMcPsTR1eW12/fn1TAAAAFI1pAIAdtra2iPOagwYNkm3btpkGsjaMdcsrHXEOJyXbuHGjyfAd9tRTT5ks4JdccknMdXSf6nvuuScx7wEAAL9wLMR7bwxM05gGAPjfsGHDTKmMJheLtn79+sNUKwAA4GVJXTOt0+cCgUCFctNNNyWzWgCARND1TrYKPINYDwA+56RurE/qyPTixYvN/p9hK1askH79+smll16azGoBAIAEIdYDAPwqqY3ppk2bxjzWLUiOO+44OfPMMys9v6yszJSw0tJS63UEANRMwPmx2LguvINYDwD+FrAQ770S612zNZYme3n++efl6quvNtO/KqOZVrOzsyMlJyfnsNcTAFBNTPNGOcR6APAhJ3VjvWsa07Nnz5YdO3bIVVddVeU5o0aNkp07d0ZKSUnJYa0jAACoOWI9AMBPXJPNe+rUqdK/f39p2bJlledkZmaaAgBwv0Dox2LjuvAmYj0A+E/AQrz3Sqx3RWN6w4YNMn/+fHn55ZeTXRUAAGABsR4A4DeuaExPnz5dmjVrJhdccEGyqwIASBRba548so4KsYj1AOBTjoV475FYn/Q106FQyATYgoICqVXLFW17AACQQMR6AIAfJT2i6ZSvjRs3msyeAAAf0U5lGx3L3uisRhRiPQD4mGMhNnsk1ie9MX3eeeeJ45FhfAAAED9iPQDAj5LemAYA+FPAcUyxcV0AAODfeB/wSKxP+pppAAAAAAC8hpFpAIAdZPMGAMD/nNTN5k1jGgBgh8bBkKXrAgAA/8Z7RzyBad4AAAAAAMSJkWkAgBUkIAMAwP8CJCADAAAAAADVxcg0AMAO7VS2koAs8ZcEAAAuiveOeAIj0wAAAAAAxImRaQCAHWyNBQCA/zmpuzUWI9MAAAAAAMSJkWkAgB2652TA0nUBAIB/431IPIHGNADACrbGAgDA/wIpvDWWpxvTzk8f8g+y3zMZ35BINoa8LPDIlwHsKP3e3V2rpbtCMd+ngNsQ64HEcoJlya6C77g91ivivR2ebkx///335s8PZE6yq4Jk4LsAHtConXjm+zQ7OzuxFyUBGRKAWA8k2KpkV8B/vBLrPRXvnfivN3HiRHnkkUdk8+bN0rVrV/njH/8oPXr0qPTclStXyujRo2XJkiWyYcMGefzxx+XWW29NrcZ0y5YtpaSkRBo0aCCBQGJGKUtLSyUnJ8dcNysrS9zMK3WlnqlZTy/VNZXrqT3UGlj1+xRIlVif6v/ubaCeqVtX6umNevo93s+aNUsKCwtl0qRJ0rNnT5kwYYLk5eXJ6tWrpVmzZhXO37Nnjxx77LFy6aWXyogRI2r8up5uTKelpcnRRx9t5dr6y+vmf2herCv1TM16eqmuqVrPhPdQhzEyDZfH+lT+d28L9UzdulJP99fTU/Heie9648ePl6FDh8qQIUPMY21Uv/HGGzJt2jQZOXJkhfNPOeUUU1RlP68utsYCAAAAALhypL40qpSVVVzzv2/fPjNdu2/fvjEdsfp44cKFVutHYxoAYLen2kYBAADu4NiL9TrlXUfUw6WoqKjCy2/fvl2CwaA0b9485rg+1vXTNnl6mrcNmZmZMmbMGPOn23mlrtQzNevppbpSTyD1eOXfE/VMzXp6qa7UMzXrebiUlFs77rbPJeCQHx0AkEA6DUt7j89t/zuplZ74oPdDsEwWrH5Mdu7c6Yl1bwAA+FGpxXgfT6zXad5169aVl156SQYOHBg5XlBQIDt27JBXX331gM9v27atyeRdk2zeTPMGAFgRcBxrBQAAuEMgybE+IyNDcnNzZcGCBZFjoVDIPO7Vq5fYxDRvAAAAAIBnFRYWmpHo7t27m72ldWus3bt3R7J75+fnS6tWrSJrrnU0+7///W/k/zdt2iTLli2T+vXry/HHH1/t16UxDQCwg62xAADwPyf5W2MNGjRItm3bJqNHjzZJx7p16yZz586NJCXbuHGjyfAd9tVXX8nJJ58cefzoo4+acuaZZ0pxcXG1X5fGNAAAAADA04YNG2ZKZco3kHWddCJSh7FmupyJEyeaD7dOnTrSs2dPWbRokbjNe++9JwMGDJCWLVtKIBCQ2bNni9voFArdCL1BgwbSrFkzkwxg9erV4kZPPfWUdOnSxSQ30KJrK958801xuwcffND8/dckWYJN99xzj6lXdOnQoYO4kU7p+c1vfiNHHnmkHHHEEdK5c2f55JNPxG30O6n8Z6rlpptuElcLOfYKcAiI9akX74n1iUe8TyzPxnqVwrGexnSUWbNmmfn2mo5+6dKl0rVrV8nLy5OtW7eKm+j8f62b3gy41bvvvmv+8X/00Ufy1ltvyf79++W8884zdXebo48+2gQr3exdv1jPOeccueiii2TlypXiVosXL5ann37a3Bi40UknnSRff/11pHzwwQfiNt99952cdtppUrt2bXNDpetmHnvsMWnUqJG48e87+vPUf1Pq0ksvTXbVAM8h1qdmvCfW20G8TxxivTexNVYU7Z3W3tUnnngikgVONwq/+eabZeTIkeJG2mP1yiuvxKSBdyNdw6A91hp0zzjjDHG7xo0byyOPPCLXXHONuM2uXbvkZz/7mTz55JNy//33mzUhmmTBTT3VOoKiSRzcTP9N//Of/5T3339fvEZHKF5//XX5/PPPzXeAW7fK6HvscGtbY81f+3u2xkKNEOvt8lK8J9YfGuJ9asd62/H+B4/Eekamf6JZ3LS3sm/fvpFjukhdHy9cuDCpdfMD/YcQDlxuFgwGZebMmaZH3XYq/ZrSEYALLrgg5nfVbfSLX6cmHnvssXLFFVeYpA9u89prr5mMj9rjqzd+moRiypQp4oXvqueff16uvvpq1wZXwK2I9fZ5Id4T6xOHeG8Hsd47SED2k+3bt5sv13DGtzB9/OmnnyatXn6gvf7au6ZTbDp16iRutHz5chNQ9+7da1Li6whAx44dxW00+Ou0RJ0K5OZRn2effVbat29vpinde++90qdPH1mxYoVZU+cWa9euNWvodLrnHXfcYT7TW265xexVqFsruJWOAuzYsUOuuuoqcT9L2bz1ukANEOtTO94T6xOLeG+Pt2K9rXjvjVhPYxqHpXdVv1jduI4mTAOBTlPSHvWXXnrJfLnqFDU3BdmSkhIZPny4WUOjSXPcqn///pH/13VeGmzbtGkjf/nLX1w1lU5v+rSnety4ceax9lTr7+mkSZNcG1zV1KlTzWesIwGux9ZYQEpxe7wn1icW8d4eT8V6l2yNlSxM8/5JkyZNJD09XbZs2RJzXB+3aNEiafXyOk1Pr+s93nnnHZP8w620d1I3aM/NzTWZSTXpy+9//3txE52aqAlydA1VrVq1TNGbgD/84Q/m/3W0xY0aNmwo7dq1kzVr1oibHHXUURVuoE488URXTlEL27Bhg8yfP1+uvfbaZFcF8CRifWrHe2K9XcT7xCDWewuN6agvWP1yXbBgQUxPlj5263oaN9O8dhpYdQrV22+/Lcccc4x4if7dl5WViZuce+65Zoqa9qqHi/a06hol/X+9QXQjTaLyxRdfmGDmJjoNsfz2LZ999pnpVXer6dOnm/Veuo7OE9gaCy5DrE88L8d7Yn1iEe9TNNarFI71TPOOomspdLqHfmn16NHDZE3U5BRDhgwRt31ZRff6rVu3znzBarKP1q1bi1umes2YMUNeffVVs25m8+bN5rhm/NP9/dxk1KhRZiqNfnbff/+9qbdu7D5v3jxxE/0cy69Bq1evntkz0U1r02677TazN6oGqa+++spsP6PBf/DgweImI0aMkN69e5tpX5dddpnZZ3by5MmmuPWmTwOsfkfp6ASAmiHWp2a8J9YnHvE+8Yj13sPfUpRBgwaZLR1Gjx5tgoFuQzB37twKiUqSTfdHPPvss2NuDJT+w9NEEG6giR7UWWedFXNcvyDclkxBp1Pl5+eb5Bka/HXdjwbXfv36JbtqnvTll1+aQPrNN99I06ZN5fTTTzf7j+r/u4lujaMjKXqDdd9995nRFL2p1t5/N9IpXzolTTN7eoYT+rHYuC5QQ8T61Iz3xPrEI94nnidjva1475FYzz7TAAA7+062vlFqpVnYZzpUJvM3Pun6vScBAPCzUovx3iuxnpFpAIAdZPMGAMD/HLJ5AwAAAACAamJkGgBgh8nEaaFn2SMZPgEASAkhC/HeI7GexjQAwA6meQMA4H8O07wBAAAAAEA1MTINALDDzPqyMTKd+EsCAAAXxXtHPIGRaQAAAAAA4sTINADADtZMAwDgfw5rpgEAAAAAQDXRmAaqUFJSIldffbW0bNlSMjIypE2bNjJ8+HD55ptvkl01wBtCIXsFABKAWA8kQCh1Yz2NaaASa9eule7du8vnn38uL774oqxZs0YmTZokCxYskF69esm3335r7bX37dtn7doAAOBHxHoAh4rGNFCJm266yfRQ/+Mf/5AzzzxTWrduLf3795f58+fLpk2b5M477zTnBQIBmT17dsxzGzZsKM8++2xMr/dll11mjjdu3FguuugiWb9+feTnV111lQwcOFAeeOAB0zPevn17ue+++6RTp04V6tWtWze5++67rb53IOFrqGwUADhExHogQZzUjfU0poFytCd63rx5cuONN8oRRxwR87MWLVrIFVdcIbNmzRKnGv/I9+/fL3l5edKgQQN5//335Z///KfUr19ffv7zn8f0Smsv+OrVq+Wtt96S119/3Uw5W7VqlSxevDhyzr/+9S/5z3/+I0OGDEnwOwYsoTENwKWI9UACOakb68nmDZSj0700eJ544omV/lyPf/fdd7Jt27aDXksDcSgUkmeeecb0bKvp06ebnuvi4mI577zzzLF69eqZc7SHPEwDs557yimnRJ6nPefHHntsgt4pAACpiVgPIBEYmQaqcLDe6OhgWJV///vfZg2W9lZrL7UWnf61d+9e+eKLLyLnde7cucL1hg4datZw6bnasz1jxgzTiw14RsixVwAgAYj1QAKEUjfWMzINlHP88cebnmWdenXxxRdX+Lkeb9q0qelx1vPKB2Kd7hW2a9cuyc3NlRdeeKHCdfQaYdpbXd6AAQMkMzNTXnnlFRN89bqXXHJJAt4hAACpjVgPIBFoTAPlHHnkkdKvXz958sknZcSIETFrqTZv3myCpSYtCQfJr7/+Omba2J49eyKPf/azn5npX82aNZOsrKy46lGrVi0pKCgwU740wP7617+usK4LcDPHCZli47oAcCiI9YC7473jkVjPNG+gEk888YSUlZWZtUzvvfeeydI5d+5cE3jbtWsno0ePNuedc8455lxNGPLJJ5/I9ddfL7Vr145cRxOYNGnSxGT11KQk69atM+unbrnlFvnyyy8PWo9rr71W3n77bfPaTPsCACBxiPUADhWNaaASJ5xwgsmuqQlAdKuLNm3amO0yNLiGs3Sqxx57THJycqRPnz5y+eWXy2233SZ169aNXEf/XwO0brfxy1/+0iQ0ueaaa8zaqOr0Xms9evfuLR06dJCePXtafc9AwjmW1lB5JMMnAHcj1gMujveON2J9wKlOzn8AMmbMGBk/frzZ0uLUU089LK+p/zw1yOrWHYWFhYflNYFDVVpaKtnZ2XJuw3ypFTh48p54/eDskwU7/iQ7d+6Me0olABwIsR5wR7z/wSOxnjXTQDXde++90rZtW/noo4+kR48ekpZmd2KHbscxc+ZMs3aL/SbhSaav1kJ/LX3AACwh1gMuifeON2I9jWkgDocz0GkiE12DNXnyZGnUqNFhe10gYUIhkYCFBCIeSUoCwJuI9YAL4r3jjVhPYxpwKVZgAADgb8R6wNtoTAMA7GCaNwAA/uek7jRvsnkDAAAAABAnRqYBAFY4oZA4FtZMOx5ZRwUAQCpwLMR7r8R6RqYBAAAAAIgTI9MAADtYMw0AgP85rJkGAAAAAADVxMg0AMCOkCMSYGQaAABfC1mI9x6J9TSmAQB2mEBoIYGIRwIsAAApwbEQ7z0S65nmDQAAAABAnBiZBgBY4YQccSxM83Y80lsNAEAqcCzEe6/EekamAQAAAACIEyPTAAA7nJClNdMWrgkAANwT7x1vxHpGpgEAAAAAiBONaQCAvTVUlgoAAHAHxyWxfuLEidK2bVupU6eO9OzZUxYtWnTA8//6179Khw4dzPmdO3eWOXPmxP2aNKYBAAAAAJ41a9YsKSwslDFjxsjSpUula9eukpeXJ1u3bq30/A8//FAGDx4s11xzjfzrX/+SgQMHmrJixYq4XjfgeCVVGgDAE0pLSyU7O1vOkoukVqB2wq//g7NfiuVV2blzp2RlZSX8+gAAILnx/oc4Y72ORJ9yyinyxBNPmMehUEhycnLk5ptvlpEjR1Y4f9CgQbJ79255/fXXI8dOPfVU6datm0yaNKna9SQBGQDAih9kv4hj6boAAMC38f6Hn2K9NtijZWZmmhJt3759smTJEhk1alTkWFpamvTt21cWLlxY6fX1uI5kR9OR7NmzZ8dVTxrTAICEysjIkBYtWsgHm+Nfe1Rden19HQAA4M94X79+fTO6HE2ncd9zzz0xx7Zv3y7BYFCaN28ec1wff/rpp5Vee/PmzZWer8fjQWMaAJBQmshj3bp1pqfYZgDX1wEAAP6M947jSCAQiDlWflQ62WhMAwCsBFgauwAA+FsdF8T7Jk2aSHp6umzZsiXmuD7WkfPK6PF4zq8K2bwBAAAAAJ6UkZEhubm5smDBgsgxTUCmj3v16lXpc/R49PnqrbfeqvL8qjAyDQAAAADwrMLCQikoKJDu3btLjx49ZMKECSZb95AhQ8zP8/PzpVWrVlJUVGQeDx8+XM4880x57LHH5IILLpCZM2fKJ598IpMnT47rdWlMAwAAAAA8a9CgQbJt2zYZPXq0SSKmW1zNnTs3kmRs48aNJsN3WO/evWXGjBly1113yR133CEnnHCCyeTdqVOnuF6XfaYBAAAAAIgTa6YBAAAAAIgTjWkAAAAAAOJEYxoAAAAAgDjRmAYAAAAAIE40pgEAAAAAiBONaQAAAAAA4kRjGgAAAACAONGYBgAAAAAgTjSmAQAAAACIE41pAAAAAADiRGMaAAAAAACJz/8H4xhXLYpQ8jQAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 1200x600 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# loc.shape = (bs, seq_len, n_points, 2d)\n",
    "# 重建可变形注意力的完整注意力权重\n",
    "full_score = torch.zeros(8, 8)\n",
    "for i in range(8):\n",
    "    for j in range(n_points-1, -1, -1):\n",
    "        idx = max(0, min(7, int(loc[0, i, j, 0].item() + 0.5)))\n",
    "        full_score[idx, i] = deformable_score[0, i, j].item()\n",
    "\n",
    "# 用热力图绘制两张注意力权重\n",
    "plt.figure(figsize=(12, 6))\n",
    "\n",
    "plt.subplot(1, 2, 1)\n",
    "plt.imshow(classic_score[0], interpolation='nearest')\n",
    "plt.colorbar()\n",
    "plt.xlabel('Query')\n",
    "plt.ylabel('Key')\n",
    "plt.title('classic attention map')\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "plt.imshow(full_score, interpolation='nearest')\n",
    "plt.colorbar()\n",
    "plt.xlabel('Query')\n",
    "plt.ylabel('Key')\n",
    "plt.title('deformable attention map')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "random_indexes tensor([2, 6, 7, 1, 4, 0, 3, 5])\n",
      "== deformable attention ==\n",
      "output shape torch.Size([1, 8, 16])\n",
      "deformable attention score shape torch.Size([1, 8, 3])\n"
     ]
    }
   ],
   "source": [
    "class DeformableAttention(nn.Module):\n",
    "    \"\"\"可变形注意力，这里同样是1维的单头注意力，略去Q、K、V和输出的投影\"\"\"\n",
    "    def __init__(self, hidden_size: int = 16, n_points: int = 2):\n",
    "        super(DeformableAttention, self).__init__()\n",
    "        self.hidden_size = hidden_size\n",
    "        self.n_points = n_points  # 可变形注意力的采样点数量\n",
    "        # 用于估计偏移量,和图中的对应\n",
    "        self.sampling_offsets = nn.Linear(hidden_size, n_points * 1 * 2)  # n_points个偏移量 * n_heads * 2d\n",
    "        # 用于估计权重，和图中的对应\n",
    "        self.attention_weights = nn.Linear(hidden_size, n_points * 1)  # n_points个权重 * n_heads\n",
    "\n",
    "    def esitimate_offset_and_weights(self, q: torch.Tensor, reference_points: torch.Tensor):\n",
    "        \"\"\"根据查询，估计偏移量\n",
    "        Args:\n",
    "            q: Query，形状为(batch_size, sequence_length, hidden_size)\n",
    "            reference_points: 参考点，形状为(batch_size, sequence_length, 2)\n",
    "        Returns:\n",
    "            offset: 偏移量，形状为(batch_size, sequence_length, n_points, 2)\n",
    "            weights: 权重，形状为(batch_size, sequence_length, n_points)\n",
    "        \"\"\"\n",
    "        # 估计偏移量\n",
    "        offset = self.sampling_offsets(q)\n",
    "        # 估计权重\n",
    "        weights = self.attention_weights(q)\n",
    "        # 权重归一化\n",
    "        weights = F.softmax(weights, dim=-1)\n",
    "        return offset.reshape(q.shape[0], q.shape[1], self.n_points, 2), weights\n",
    "\n",
    "    def ground_truth_offset_and_weights(self, q: torch.Tensor, reference_points: torch.Tensor):\n",
    "        \"\"\"这里为了演示，直接用真实的偏移量，而非去训练一个线性层来估计偏移量\"\"\"\n",
    "        # 计算偏移量\n",
    "        # random_offset.shape = (batch_size, sequence_length, n_points, 2)\n",
    "        bs, seq_len , _ = q.shape\n",
    "        random_offset = torch.randint(0, seq_len, (bs, seq_len, self.n_points, 2))\n",
    "        random_offset[:, :, :, 1] = 0. #y方向的偏移量为0\n",
    "        random_offset[:, :, 1, 0] = random_offset[:, :, 1, 0] - reference_points[:, :, 0] * seq_len\n",
    "        ground_truth_offset = random_indexes - reference_points[:, :, 0] * seq_len #random_indexes是我们真实的偏移量\n",
    "        random_offset[:, :, 0, 0] = ground_truth_offset #ground_truth_offset 表示第一个点的真实偏移量，并将其赋值给 random_offset 的相应位置。最终 offset 是包含所有偏移量的张量。\n",
    "        offset = random_offset\n",
    "        # offset.shape = (batch_size, sequence_length, n_points, 2)\n",
    "\n",
    "        # 计算权重\n",
    "        weights = torch.ones(offset.shape[:-1])\n",
    "        weights[:, :, 0] = 0.8\n",
    "        weights[:, :, 1:] = 0.2 / (self.n_points - 1)\n",
    "        return offset, weights\n",
    "\n",
    "    def forward(self,\n",
    "                q: torch.Tensor,\n",
    "                v: torch.Tensor,\n",
    "                reference_points: torch.Tensor,\n",
    "                input_spatial_shapes: torch.Tensor,\n",
    "                using_ground_truth: bool = False):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            q: Query，形状为(batch_size, sequence_length, hidden_size)\n",
    "            v: Value，形状为(batch_size, sequence_length, hidden_size)\n",
    "            reference_points: 参考点，形状为(batch_size, sequence_length, 2)\n",
    "            input_spatial_shapes: 输入的空间形状，这个例子中为 (sequence_length, 1)\n",
    "            using_ground_truth: 布尔值，是否使用真实的偏移量和权重。\n",
    "        Returns:\n",
    "            output: 输出，形状为(batch_size, sequence_length, hidden_size)\n",
    "        \"\"\"\n",
    "        # 估计偏移量和权重\n",
    "        if using_ground_truth:\n",
    "            sampling_offsets, weights = self.ground_truth_offset_and_weights(q, reference_points)\n",
    "        else:\n",
    "            sampling_offsets, weights = self.esitimate_offset_and_weights(q, reference_points)\n",
    "        # sampling_offsets.shape = (batch_size, sequence_length, n_points, 2)\n",
    "        # weights.shape = (batch_size, sequence_length, n_points)\n",
    "\n",
    "        # 获得采样点，sampling_locations 的形状为 (batch_size, sequence_length, n_points, 2)。\n",
    "        offset_normalizer = input_spatial_shapes\n",
    "        sampling_locations = reference_points[:, :, None, :] + sampling_offsets / offset_normalizer[None, None, None, :] #计算后sampling_locations尺寸为（1，8，1，2）\n",
    "\n",
    "        # 获得采样点的绝对位置\n",
    "        sampling_locations_absolute = sampling_locations * input_spatial_shapes[None, None, None, :]\n",
    "\n",
    "        # 根据[0~1]的采样点，反归一化到输入序列的长度\n",
    "        # v.shape bs, seq_len, hidden_size -> bs, hidden_size, seq_len（1,16,8）\n",
    "        v = v.permute(0, 2, 1)\n",
    "        # 使用 grid_sample 从值 v 中采样特征，并调整形状以适应加权求和。sampled_values 的形状为 (batch_size, sequence_length, n_points, hidden_size)\n",
    "        sampled_values = F.grid_sample(v.unsqueeze(-1), sampling_locations, align_corners=True)\n",
    "        # sampled_values.shape = (bs, hidden_size, seq_len, n_points) -> (bs, seq_len, n_points, hidden_size)\n",
    "        sampled_values = sampled_values.permute(0, 2, 3, 1)\n",
    "        # 对采样的特征值进行加权求和，得到最终的输出 output，形状为 (batch_size, sequence_length, hidden_size)。\n",
    "        output = torch.sum(sampled_values * weights.unsqueeze(-1), dim=-2)\n",
    "\n",
    "        return output, (sampling_locations_absolute, weights)\n",
    "\n",
    "\n",
    "# 生成随机数据\n",
    "dummy_query = torch.randn(1, 8, 16)  # batch_size=1, sequence_length=8, hidden_size=16\n",
    "dummy_value = torch.randn(1, 8, 16)  # batch_size=1, sequence_length=8, hidden_size=16\n",
    "# 位置索引，为了保留原始图片的位置信息\n",
    "indexes = torch.tensor([0, 1, 2, 3, 4, 5, 6, 7]).unsqueeze(0)\n",
    "# 随机索引\n",
    "random_indexes = torch.randperm(8)\n",
    "print(\"random_indexes\", random_indexes)\n",
    "# 这里的 key 是 query 的一个随机排列\n",
    "dummy_key = dummy_query[:, random_indexes]\n",
    "\n",
    "\n",
    "\n",
    "# 初始化可变形注意力\n",
    "n_points = 3\n",
    "deformable_attention = DeformableAttention(n_points=n_points)\n",
    "# 计算参考点\n",
    "reference_points = torch.tensor([\n",
    "    [0, 0],\n",
    "    [1, 0],\n",
    "    [2, 0],\n",
    "    [3, 0],\n",
    "    [4, 0],\n",
    "    [5, 0],\n",
    "    [6, 0],\n",
    "    [7, 0]\n",
    "]).reshape(1, 8, 2)  # batch_size=1, sequence_length=8, 2D\n",
    "reference_points = reference_points / 8 # 参考点的值在 0~1 之间\n",
    "\n",
    "# 计算注意力,在bevformer的decoder中，q是随机的，v是encoder的输出，k是空的\n",
    "output, (loc, deformable_score) = deformable_attention(\n",
    "    q=dummy_query,\n",
    "    v=dummy_value,\n",
    "    reference_points=reference_points,\n",
    "    input_spatial_shapes=torch.tensor([8, 1]),\n",
    "    using_ground_truth=True\n",
    "    )\n",
    "\n",
    "print(\"== deformable attention ==\")\n",
    "print(\"output shape\", output.shape)\n",
    "print(\"deformable attention score shape\", deformable_score.shape)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
